package org.sloth.mx.astar
{
	import flash.display.BitmapData;
	import flash.geom.Point;

	/**
	 * A星得法计算路线
	 * 
	 */	
	public class Astar
	{
//============================================================================
//STATIC
//============================================================================
		public static const SORT_FIELD:String = "feeTotal";
//============================================================================
//PROPERTY
//============================================================================
		private static var _parser:IAStarParser = new AStarParserEight();
//============================================================================
//PUBLIC
//============================================================================
		public static function getPath(start:Point, end:Point, bm:BitmapData):Array
		{
			if (bm == null) return [];
			
			//定义队列
			var openedList:Array = [];//已打开节点队列
			var uidVOMapOpened:Object = {};//已打开节点映射
			var uidVOMapClosed:Object = {};//已关闭节点映射
			
			//初始化初始和结束节点
			var startVO:AStarVO = parser.getVO(start);
			var endVO:AStarVO = parser.getVO(end);
			startVO.feeFrom = 0;
			startVO.feeTo = parser.getFeeTo(startVO, endVO);
			endVO.feeFrom = parser.getFeeFrom(startVO, endVO);
			endVO.feeTo = 0;
			if (!startVO || !endVO || start.equals(end)) return [];
			if (startVO.equal(endVO)) return [start, end];
			if (!parser.getMovable(endVO, bm)) return [];
			
			//初始化打开队列
			openedList.push(startVO);
			uidVOMapOpened[startVO.uid] = startVO;
			
			//定义循环变量
			var curVO:AStarVO;//当前节点
			var tempVO:AStarVO;//临时节点变量
			var loopVO:AStarVO;//循环遍历节点变量
			var arounds:Array;//当前节点相邻可移动节点集合
			var hasFound:Boolean = false;//是否找到路径
			var tempFee:Number;//保存节点代价的模拟计算值
			var isOutOfOrder:Boolean;//标识打开列表是否需要重新排序
			var index:int;
			var len:int;
			//循环打开队列，寻找路径
			while (openedList.length > 0)
			{
				//更新当前节点
				curVO = openedList.pop();
				//更新关闭队列
				uidVOMapClosed[curVO.uid] = curVO;
				//如果当前节点即为目标节点，完成
				if (curVO.equal(endVO))
				{
					hasFound = true;
					break;
				}
				//获取当前节点的相邻可移动节点集合
				arounds = parser.getArounds(curVO);
				index = arounds.length - 1;
				while (index > - 1)
				{
					loopVO = arounds[index];
					if (!parser.getMovable(loopVO, bm)) arounds.splice(index, 1);
					index--;
				}
				//遍历当前节点相邻可移动节点
				len = arounds.length;
				for (index = 0;index < len;index++)
				{
					loopVO = arounds[index];
					if (uidVOMapClosed[loopVO.uid]) continue;//如果循环节点已在关闭队列，遍历下一个节点
					tempVO = uidVOMapOpened[loopVO.uid];//在打开队列中查找循环节点
					if (tempVO)//如果循环节点已在打开队列中
					{
						//计算从当前节点到循环节点（在打开队列中的节点VO）的实际代价
						tempFee = curVO.feeFrom + parser.getFeeFrom(curVO, tempVO);
						//如果从当前节点到循环节点的实际代价小于循环节点的已知实际代价，更新循环节点的实际价值和路径（parent）
						if (tempFee < tempVO.feeFrom)
						{
							tempVO.parent = curVO;
							tempVO.feeFrom = tempFee;
							
							isOutOfOrder = true;//标识需要重新排序打开队列
						}//否则什么都不做
					}
					else//如果循环节点不在打开队列中，计算新节点的实际代价和估价，设置其路径，并将其添加到打开队列中
					{
						loopVO.parent = curVO;
						loopVO.feeFrom = curVO.feeFrom + parser.getFeeFrom(curVO, loopVO);
						loopVO.feeTo = parser.getFeeTo(loopVO, endVO);
						
						openedList.push(loopVO);
						uidVOMapOpened[loopVO.uid] = loopVO;
						
						isOutOfOrder = true;//标识需要重新排序打开队列
					}
					//在需要的情况下排序打开单元块列表
					if (isOutOfOrder) openedList.sortOn(SORT_FIELD, Array.DESCENDING | Array.NUMERIC);
				}
			}
			//查找目标节点
			var path:Array = [];
			if (hasFound)//如果已找到路径
				curVO = uidVOMapClosed[endVO.uid];
			else//如果未找到路径
				curVO = getClosestVO(uidVOMapClosed);
			//查找路径
			
			var vector1:Point = new Point();
			var vector2:Point = new Point();
			do {
				if (path.length > 1)
				{
					tempVO = path[path.length - 1];
					loopVO = path[path.length - 2];
					vector1.x = curVO.x - tempVO.x;
					vector1.y = curVO.y - tempVO.y;
					vector2.x = tempVO.x - loopVO.x;
					vector2.y = tempVO.y - loopVO.y;
					if (isSimilar(vector1, vector2)) path.pop();
				}
				path.push(curVO);
				curVO = curVO.parent;
			}while (curVO);
			
			var result:Array = [];
			for (index = path.length - 1;index >= 0;index--)
			{
				result.push(parser.getPoint(AStarVO(path[index])));
			}
			result.splice(0, 1, start);
			if (hasFound) result.splice(result.length - 1, 1, end);
			return result;
		}
//============================================================================
//PRIVATE
//============================================================================
		private static function isSimilar(v1:Point, v2:Point):Boolean
		{
			return v2.y * v1.x == v2.x * v1.y;
		}
		/**
		 * 在指定队列中查找一个估价最小的节点
		 * @param idVOMap
		 * @return 
		 * 
		 */		
		private static function getClosestVO(uidVOMap:Object):AStarVO
		{
			var key:String;
			var vo:AStarVO;
			var keyFound:String;
			var curFee:Number = Number.MAX_VALUE;
			for (key in uidVOMap)
			{
				vo = uidVOMap[key];
				if (vo.feeTo < curFee)
				{
					keyFound = key;
					curFee = vo.feeTo;
				}
			}
			return uidVOMap[keyFound];
		}
//============================================================================
//GETTER/SETTER
//============================================================================
		/** 地图解析器，默认八方向寻路 */
		public static function get parser():IAStarParser
		{
			return _parser;
		}

		/**
		 * @private
		 */
		public static function set parser(value:IAStarParser):void
		{
			if (value == null) return;
			_parser = value;
		}

	}
}